A. Field of the Invention
The invention relates generally to the technical field of protection from spying out in portable data carriers. More specifically the invention relates to the technical area of preventing the spying out of data to be kept secret when a portable data carrier executes an operation sequence and cache accesses take place in the process. A portable data carrier within the meaning of the present document can e.g. be a chip card (smart card) of different construction types or a chip module or other limited-resource system with at least a processor core, a main memory and a cache memory.
B. Related Art
Portable data carriers are frequently employed for security-critical applications, for example in financial transactions, for authentication in mobile communication, as signature card for electronic signature and so on. Since great damage could be caused by unauthorized use, secret data that are stored on such data carriers must be reliably protected from spying out and manipulation.
Various attack methods are known, in which physical parameters of the data carrier are measured during the program execution, so as to draw conclusions regarding data to be kept secret. For example in simple power analysis (SPA) the current consumption of the data carrier during a computation process is measured and examined. In contrast, in differential power analysis (DPA) the current consumption is statistically evaluated over a plurality of computation processes.
The above-mentioned attacks are generally referred to as side channel attacks, since the information flow does not take place via the primary communication channel of the data carrier, but bypassing it. Chapter 16.5.1 of the book “Handbuch der Chipkarten” (“Handbook of chip cards”) by W. Rankl and W. Effing, Hanser Verlag, 5th edition, 2008, pages 740-771, gives an overview of various attack and thwarting methods. The thwarting of side channel attacks is also the object of various patent documents, such as for example of the publication prints DE 198 22 218 A1, WO 99/35782 A1, WO 99/67919 A2 and U.S. 2002/0124178 A1.
Examinations have shown that in high-performance data carriers having a cache memory there are additional possibilities for side channel attacks. For it is generally possible to determine on the basis of the time response and/or the current consumption pattern upon program execution whether a cache hit or a cache miss occurs. From this information in turn conclusions can be drawn regarding data to be kept secret, provided that these data are correlated with the executed operation sequence—and in particular with the data values that are accessed in this operation sequence.
As an example for an operation sequence in danger of spying out, the modular exponentiation of a data value v1 with an exponent d according to the well-known “square and multiply” method should be mentioned. This method is for example described as method 2.143 in the book “Handbook of applied cryptography” by A. Menezes, P. van Oorschot and S. Vanstone, CRC Press, 1996, page 71. A modular exponentiation is e.g. used in RSA computations. The exponent d forms the private RSA key and must therefore be protected from spying out.
The computation of v1d mod N according to the “square and multiply” method takes place in a loop, which is run through respectively once for each bit of the exponent d—starting with the most significant bit. Upon each cycle of the loop first an intermediate value v2 is squared.
If the contemplated bit of the exponent d has the value “1”, further the intermediate value v2 is multiplied with the data value v1. In total the following method results; the bit positions of the exponent d are designated by d(i) for i=0, 1, . . . , k, so that d=Σi=0, 1, . . . , k d(i)·2i applies:    SET v2:=1    FOR i=k, (k−1), . . . , 1, 0, EXECUTE            SET v2:=v2·v2 mod N        IF d(i)=1 THEN SET v2:=v2·v1 mod N        
After the computation process v2=v1d mod N applies. The access pattern to the data values v1 and v2 during the computation depends on the bits of the exponent d to be kept secret.
The data values v1 and v2 can for example have a size of 256 bytes (2048 bits) each. In portable data carriers the cache memory is generally relatively small and can e.g. have a size of 2 Kbytes. If the cache memory is already partly occupied by other data, then there is possibly sufficient space only for one of the two data values v1 and v2—but not for both. In this case at least one cache miss results in every loop cycle with d(i)=1, since at least the data value v1 must first be loaded. Upon consecutive loop cycles with d(i)=0, in contrast no cache misses occur, since it is always only the data value v2 that is accessed. As already mentioned it is to be expected that cache misses are recognizable from the power profile, so that an attacker can draw conclusions regarding the bits of the exponent d.
In some micro controllers special commands are provided to hold data in the cache permanently; this is referred to as “blocking” of the cache. Then, upon each access of the blocked data then exclusively cache hits occur. However, the volume of securely processable data is limited to the size of the cache. It would be desirable not to be subjected to this limitation.
Other micro controllers do not have any cache block commands. It would be desirable to reliably prevent attacks of the above-mentioned type also in this case.
Accordingly it is the object of the invention to solve the above-mentioned problems entirely or partly and to create a technology for protecting an operation sequence executed by a portable data carrier from spying out, wherein the attack scenario to be thwarted is based on an evaluation of the cache accesses—in particular of the cache hits and cache misses—during the execution of the operation sequence. In preferred embodiments the invention should also be applicable when the operation sequence accesses large data volumes or when the data carrier does not support cache block commands.